package zuoshen_video;

import linked.ListNode;

public class LinkedListProblems {
    
    //1.找到环入口
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if (fast == null || fast.next == null) return null; //无环
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    //2.找到两个无环链表的公共节点
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        if (p == null || q == null) return null;
        int len1 = 1, len2 = 1;
        while (p.next != null) {
            p = p.next;
            len1++;
        }
        while (q.next != null) {
            q = q.next;
            len2++;
        }
        if (p != q) return null; //尾结点不是同一个对象，因此无交点
        p = headA;
        q = headB;
        if (len1 < len2) {
            ListNode t = p;
            p = q;
            q = t;
        }
        for (int i = 0; i < Math.abs(len1 - len2); i++) {
            p = p.next;
        }
        while (p != q) {
             p = p.next;
             q = q.next;
        }
        return p;
    }

    //2.简化版，两者都跑到重点，再跑对方的那一半
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        //先证明有交点吧
        if (p == null || q == null) return null;
        while (p.next != null) p = p.next;
        while (q.next != null) q = q.next;
        if (q != p) return null; //无交点
        p = headA;
        q = headB;
        while (true) {
            if (p == q) return p;
            p = p.next == null ? headB : p.next;
            q = q.next == null ? headA : q.next;
        }
    }

    //3. 有环链表，在求得两个环入口的情况下，求得其交点【三种情况】
    public ListNode getIntersectionCycleNode(ListNode headA, ListNode headB) {
        ListNode loop1 = detectCycle(headA);
        ListNode loop2 = detectCycle(headB);

        if (loop1 == null && loop2 == null) {
            //证明都不存在环结构，尝试使用无环链表的方式寻找公共节点
            return getIntersectionNode(headA, headB);
        } else if (loop1 == null || loop2 == null) {
            //一个有环，一个没环，肯定没有交点
            return null;
        } else {
            //三种情况
            //从loop1开始，到下次遇到loop1为止，如果中途遇到loop2，证明是情况三【羊角型】；
            //没遇到loop2, 两个环无交点
            //loop1 == loop2[同一个对象]， 环入口就是交点
            if (loop1 == loop2) return loop1;
            else {
                ListNode cur = loop1.next;
                while (cur != loop1 || cur != loop2) {
                    cur = cur.next;
                }
                if (cur == loop2) return loop1; //羊角形状，返回其中一个环入口作为公共交点即可
                else return null;
            }
        }
    }
}
